package com.zlk.algorithm.dataStructure.linkList03;


import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName IsPalindromeList
 * @description:给定一个单链表的头节点head，请判断该链表是否为回文结构
 * eg   12  3  21   利用容器栈实现很简单
 * https://leetcode.cn/problems/palindrome-linked-list/
 * @author: slfang todo
 * @create: 2024-02-01 10:27
 * @Version 1.0
 **/
public class Code08_IsPalindromeList {

     public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }


  @Test
  public void test(){
      ListNode l1 = new ListNode(1);
      ListNode l2 = new ListNode(1);
      ListNode l3 = new ListNode(2);
      ListNode l4 = new ListNode(1);

      l1.next=l2;
      l2.next=l3;
      l3.next=l4;

      ListNode lc = l1;
      lc.next = null;

      System.out.println(isPalindrome(l1));
  }


    ///// 1、利用栈
    //利用快慢指针  中点指向 null
    //   1 2 3 4 5  终止条件 head==tail
    //   1 2 3 4 5 6 有一个head 走完指向null
    //
    public boolean isPalindrome(ListNode head) {
         ListNode slow = head;
         ListNode fast = head;
         while (fast.next!=null&&fast.next.next!=null){
             slow = slow.next;
             fast = fast.next.next;
         }
         ListNode head2 = slow.next;
         boolean isOdd=false;
         slow.next=null;
         if(fast.next!=null){
             isOdd = true;
         }
         //反转链表  2  1
         ListNode pre = isOdd?null:slow;
         while (head2!=null){
             ListNode temp = head2.next;
             head2.next = pre;
             pre = head2;
             head2 =temp;
         }
         ListNode l = head;
         ListNode r = pre;
         while ((l!=r)&&(l!=null&&r!=null)){
             if(l.val!=r.val){
                 return false;
             }
             l =l.next;
             r =r.next;
         }
         return true;
    }


}
